#include <bits/stdc++.h>
using namespace std;

/*
1399. 统计最大组的数目
已解答
简单
相关标签
相关企业
提示
给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。

 

示例 1：

输入：n = 13
输出：4
解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。
示例 2：

输入：n = 2
输出：2
解释：总共有 2 个大小为 1 的组 [1]，[2]。
示例 3：

输入：n = 15
输出：6
示例 4：

输入：n = 24
输出：5
 

提示：

1 <= n <= 10^4
*/

class Solution {
	public:
	int countLargestGroup(int n) {
		unordered_map<int, int> count_map; // 用于记录每个数位和出现的次数
		// 遍历从 1 到 n 的所有数字
		for (int i = 1; i <= n; i++) {
			int x = i, sum = 0;
			// 计算当前数字的各位数字之和
			while (x > 0) {
				sum += x % 10; // 提取当前数字的最后一位并累加到 sum
				x /= 10;       // 去掉当前数字的最后一位
			}
			// 在哈希表中记录该数字和出现的次数
			count_map[sum]++;
		}

		int max_count = 0; // 记录最大的组大小
		int ans = 0;       // 记录具有最大组大小的组的数量
		// 遍历哈希表以找到最大的组
		for (const auto& pair : count_map) {
			if (pair.second > max_count) {
				max_count = pair.second; // 更新最大组大小
				ans = 1;                 // 重置最大组数量计数
			} else if (pair.second == max_count) {
				ans++; // 增加最大组数量计数
			}
		}
		return ans; // 返回具有最大组大小的组的数量
	}
};